/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} startValue
 * @param {number} destValue
 * @return {string}
 */
 var getDirections = function(root, startValue, destValue) {
  // 建图
  const map = {}
  let q = [root]
  while(q.length){
    let temp = []
    for(let i = 0, len = q.length; i<len; i++){
      let cur = q.pop()
      map[cur.val] = map[cur.val] || {}
      if(cur.left){
        let v = cur.left.val
        map[cur.val][v] = 'L'
        map[v] = map[v] || {}
        map[v][cur.val] = 'U'
        temp.push(cur.left)
      }
      if(cur.right){
        let v = cur.right.val
        map[cur.val][v] = 'R'
        map[v] = map[v] || {}
        map[v][cur.val] = 'U'
        temp.push(cur.right)
      }
    }
    q = temp
  }
  // 搜索路径
  startValue = String(startValue), destValue = String(destValue)
  const path = new Map().set(startValue,'')
  const used = new Set()
  q = [startValue]
  while(q.length){
    let temp = []
    for(let i = 0, len = q.length; i<len; i++){
      let cur = q.pop()
      used.add(cur)
      let pre = path.get(cur) || ''
      if(map[cur]){
        for(let [k, v] of Object.entries(map[cur])){
          if(k === destValue){
            return pre + v
          }
          if(!used.has(k)){
            temp.push(k)
            path.set(k, pre + v)
          }
        }
      }
    }
    q = temp
  }
  return ''
};